As it is known in the art, each packet that is forwarded from a source to a destination experiences a transmission delay. The transmission delay is associated with both the route that the packet takes from the source to the destination and the delays associated with the devices that the packet encounters in transit. It is important to be able to estimate the delay for a variety of reasons. Network administrators may analyze delay data to support network planning, billing, performance monitoring and reporting, or to determine how to alter tunable network parameters to improve performance. An accurate estimate of the delay is particularly important for systems which stream real time data, such as voice and video. In such systems the source encoding process typically emits packets periodically and the destination decoding process expects to receive packets in the same periodic fashion in order to play them out properly. Jitter or variation in inter-packet timing at the receiver caused by variable transit delays must be removed by a jitter (removal) buffer. These buffers remove jitter by storing and delaying sufficient arriving packets so they can be played out periodically in the same fashion they were input to the network. The design and engineering of jitter buffers in particular and of the network in general require a good characterization of delay variation. In what follows “delay” will be a common term used to refer to either end-to-end packet transit delay or jitter (variation of inter-packet arrival delay) at the receiver.
Several problems arise when estimating network delay. One is the selection of the appropriate definition of delay. The definition employed here is the quantile, defined as follows: t is said to be the p-th quantile of a random variable T with distribution function F if F(t)=p for some probability p. Another problem is that the specific mathematical form of these distributions of delay for each component will in general not be known. Even if the delay distributions are known, whenever more than one network is traversed end-to-end, multi-dimensional convolutions are required to obtain end-to-end delays. Because multi-dimensional convolutions are generally too computationally expensive and inaccurate to perform directly, Laplace transforms are used in their place. However, Laplace transforms require mathematically complicated transform inversion techniques making them undesirable for use in routine network planning situations.